# -*-coding:utf-8-*-
'''
File Create by Author:Backpackerxl
Create File Time:2021/9/24/024 20:32
Program IDE:PyCharm
File Name:test.py

'''


#
# import sys
# sys.setrecursionlimit(10000)

# num = 12
#
#
# def sum(num_two):
#     global num
#     num = 90
#     return num + num_two
#
#
# # print(sum(10))
# #
# #
# # def many_progrm(a, b, *args):
# #     print(args)
# #
# #
# # many_progrm(11, 22, 33, 44, 55)
# XlFactorial = lambda num: num if num == 3 else num * XlFactorial(num - 1)
#
# countNum = lambda num: num if num == 2 else num + countNum(num - 2)


# def countNum(num):
#     sum = 0
#     for i in range(1, num + 1): sum += i if i % 2 == 0 else 0
#     return sum

# def isCallBackNum(num=int(input('请输入一个整数:'))):
#     cnum = num
#     call = ''
#     while cnum != 0:
#         call += str(cnum % 10)
#         cnum /= 10
#         cnum = int(cnum)
#
#     info = f'{num}是回文数' if int(call) == num else f'{num}不是回文数'
#     return info


# arr = '23569'
# list_my = [int(i) for i in arr]
# length = len(list_my)
# changeTime = int(length / 2) if length % 2 == 0 else int((length - 1) / 2)
# j = -1
# for i in range(changeTime):
#     list_my[i] = list_my[i] ^ list_my[j]
#     list_my[j] = list_my[i] ^ list_my[j]
#     list_my[i] = list_my[i] ^ list_my[j]
#     j -= 1
# print(str(list_my))

# num = int(input('请输入一个整数：'))
# print(isCallBackNum())
# countNum(5)
# print(XlFactorial(6))
# print(countNum(100))

# isTriangle = lambda *args: f'{args}能构成三角形' if args[0] + args[1] > args[2] and args[0] + args[2] > args[1] and args[1] + args[2] > args[0] else f'{args}不能构成三角形'
#
#
# print(isTriangle(3, 4, 5))

# def divisor(*args):
#     '''
#     辗转相除法，求两个数的最大公约数
#     '''
#     x = args[0]
#     y = args[1]
#     while y != 0:
#         if x < y:
#             x = x ^ y
#             y = x ^ y
#             x = x ^ y
#         t = x % y
#         x = y
#         y = t
#
#     return f'{args}的最小公倍数={int(args[0] * args[1] / x)}'
#
#
# print(divisor(int(input('please input a number:')), int(input('please input a number:'))))
# n = 4
# n /= 2
# print(n)


# def KakutaniConjecture(num):
#     '''
#     角谷猜想
#     '''
#     count = 0
#     while num != 1:
#         if num % 2 == 0:
#             num /= 2
#         else:
#             num = num * 3 + 1
#         count += 1
#
#     return count
#
#
# print(KakutaniConjecture(3))

# def fab(n):
#     if n < 1:
#         print('输入有误!')
#         return -1
#     if n == 1 or n == 2:
#         return 1
#     else:
#         return fab(n - 1) + fab(n - 2)
#
#
# if fab(20) != -1:
#     print(f'总共有{fab(15)}对兔子生成')


def mergelist(arr):
    '''
    归并排序算法
    '''
    # 拆分部分
    n = len(arr)
    if n <= 1:
        return arr
    mid = n // 2
    l_arr = mergelist(arr[:mid])
    r_arr = mergelist(arr[mid:])
    # 归并部分
    res = []
    l_pop = r_pop = 0
    l_len = len(l_arr)
    r_len = len(r_arr)
    while l_pop < l_len and r_pop < r_len:
        if l_arr[l_pop] > r_arr[r_pop]:
            res.append(l_arr[l_pop])
            l_pop += 1
        else:
            res.append(r_arr[r_pop])
            r_pop += 1

    res.extend(r_arr[r_pop:]) if l_pop == l_len else res.extend(l_arr[l_pop:])

    return res


arr = [1, 9, 13, 5, 2, 14]
print(f"给定的数组: {arr}")

print(f"排序后的数组: {mergelist(arr)}")
